﻿using System;

using System.Collections.Generic;
using System.Text;
using PublicTransport.DAL;

namespace PublicTransport.Services
{
    /// <summary>  Prvý krok vyhľadávania, ktorý je možné voľať opakovane, jeho 
    /// 		   účelom je vytvorenie zoznamu možných spojov, ktoré je možné
    /// 		   použiť pre presunte z jednej stanice do druhej </summary>
    class Step1
    {
        private ReacheableDao table;
        private readonly int penalty = 5;

        private int startStation;
        private int destinationStation;

        private int depth1 = 0;
        private int maxDepth1 = 1;
        private LinkedList<Node> open1 = new LinkedList<Node>();
        private LinkedList<Node> closed1 = new LinkedList<Node>();

        private int depth2 = 0;
        private int maxDepth2 = 1;
        private LinkedList<Node> open2 = new LinkedList<Node>();
        private LinkedList<Node> closed2 = new LinkedList<Node>();

        private Dictionary<int, Line> visitedLines = new Dictionary<int, Line>();

        /// <summary>  Prepripraví všetko pre vykonanie prvého kroku, túto inštanciu
        /// 		   je nutné ponechať a volač cez nu znova ďaľší krok, v prípade, že
        /// 		   zoznam možnosti nebude postačujúci </summary>
        ///
        /// <param name="startStation">         Štartovná zastávka </param>
        /// <param name="destinationStation">   Cieľová zastávka </param>
        /// <param name="dao">                  DAO, ktoré sa použije </param>
        public Step1(int startStation, int destinationStation, ReacheableDao dao)
        {
            this.table = dao;
            this.startStation = startStation;
            this.destinationStation = destinationStation;

            Node firstNode = new Node()
            {
                Parent = null,
                Depth = 0,
                Children = new List<Node>(),
                Info = new NodeInfo()
                {
                    ArrivalLines = new List<Line>(),
                    StationId = startStation,

                }
            };
            open1.AddFirst(firstNode);

            Node destinationNode = new Node()
            {
                Parent = null,
                Depth = 0,
                Children = new List<Node>(),
                Info = new NodeInfo()
                {
                    ArrivalLines = new List<Line>(),
                    StationId = destinationStation,

                }
            };
            open2.AddFirst(destinationNode);

        }

        /// <summary>   Vykoná jedenkrát prvý krok, to znamená, že rozvetví graf 
        /// 			v oboch smeroch, zo štartovnej a cieľovej zastávky (v konštruktore)
        /// 			a ak sa pretnú oba smery v spoločnej zastávke, tak vráti zoznam takýchto
        /// 			ciest. Cesta obsahuje zoznam spojov  </summary>
        ///
        /// <returns>   . </returns>
        public List<List<NodeInfo>> DoStep1()
        {

            List<List<NodeInfo>> totalResult = new List<List<NodeInfo>>();
            for (int i = 0; i < 1; i++)
            {
                Dictionary<int, List<Node>> result = DoStep();

                if (result.ContainsKey(destinationStation))
                {
                    List<Node> path = result[destinationStation];

                    List<NodeInfo> forwardNodes = new List<NodeInfo>();
                    Node startNode = path[0];
                    do
                    {
                        forwardNodes.Add(new NodeInfo() { StationId = startNode.Info.StationId, ArrivalLines = startNode.Info.ArrivalLines });
                        startNode = startNode.Parent;
                    } while (startNode != null);
                    forwardNodes.Reverse();
                    totalResult.Add(forwardNodes);
                }

                closed1 = new LinkedList<Node>();

                Dictionary<int, List<Node>> oppositeResult = DoOppositeStep();

                foreach (int item in result.Keys)
                {
                    if (oppositeResult.ContainsKey(item))
                    {
                        List<Node> startWay = result[item];
                        List<Node> endWay = oppositeResult[item];

                        int[] usedLines = new int[700];

                        //forward the lines 
                        List<NodeInfo> backNodes = new List<NodeInfo>();
                        Node node = endWay[0];
                        do
                        {
                            foreach (Line line in node.Info.ArrivalLines)
                            {
                                usedLines[line.LineID] = 1;
                            }
                            endWay[0].Parent.Info.ArrivalLines = endWay[0].Info.ArrivalLines;
                            backNodes.Add(new NodeInfo() { StationId = node.Info.StationId, ArrivalLines = node.Info.ArrivalLines});
                            node = node.Parent;
                        } while (node != null);
                        //remove the first node which overlaps
                        backNodes.RemoveAt(0);

                        //go to first Node
                        List<NodeInfo> forwardNodes = new List<NodeInfo>();
                        Node startNode = startWay[0];
                        bool valid = true;
                        do
                        {
                            foreach (Line line in startNode.Info.ArrivalLines)
                            {
                                if (usedLines[line.LineID] == 1)
                                {
                                    valid = false;
                                    break;
                                }
                            }
                            forwardNodes.Add(new NodeInfo() { StationId = startNode.Info.StationId, ArrivalLines = startNode.Info.ArrivalLines });
                            startNode = startNode.Parent;
                        } while (startNode != null);
                        forwardNodes.Reverse();

                        List<NodeInfo> tempResult = new List<NodeInfo>();
                        tempResult.AddRange(forwardNodes);
                        tempResult.AddRange(backNodes);

                        if (valid)
                            totalResult.Add(tempResult);

                    }
                }
                closed2 = new LinkedList<Node>();
            }
            return totalResult;
        }

        
        private Dictionary<int, List<Node>> DoStep()
        {
            Dictionary<int, List<Node>> result = new Dictionary<int, List<Node>>();
            while (depth1 < maxDepth1 || (open1.Count == 0))
            {
                //expanduj
                Node n = open1.First.Value;
                open1.RemoveFirst();
                closed1.AddLast(n);



                foreach (var item in table.GetReachableStations(n.Info.StationId, n.Info.ArrivalLines))
                {
                    Node newNode = new Node()
                    {
                        Parent = n,
                        Depth = n.Depth + 1,
                        Children = new List<Node>(),
                        Info = new NodeInfo()
                        {
                            StationId = item[0].Destination,
                        }
                    };
                    //pridavanie liniek DO
                    newNode.Info.ArrivalLines = new List<Line>();
                    foreach (var line in item)
                    {
                        Line newLine = new Line() { LineID = line.Line, Distance = line.Distance };
                        newNode.Info.ArrivalLines.Add(newLine);
                    }

                    n.Children.Add(newNode);
                    open1.AddLast(newNode);

                    if (!result.ContainsKey(newNode.Info.StationId))
                    {
                        result.Add(newNode.Info.StationId, new List<Node>());
                        result[newNode.Info.StationId].Add(newNode);
                    }
                    else
                    {
                        result[newNode.Info.StationId].Add(newNode);
                    }
                }



                //nie je idealne
                depth1 = n.Depth;
            }
            //TODO: Spytat sa martina, odoberam poslednu lebo ta nepatri do toho
            Node lastNode = closed1.Last.Value;
            closed1.RemoveLast();
            maxDepth1++;
            result.Remove(lastNode.Info.StationId);
            return result;
        }
        

        /// <summary>  Rozvetví graf z opačnej strany, teda od cieľovej zastávky. Je možné 
        /// 		   volať niekoľkokrát po sebe, udržuje si aktuálny stav </summary>
        ///
        /// <returns>   Rozvetvený zoznam</returns>
        private Dictionary<int, List<Node>> DoOppositeStep()
        {
            Dictionary<int, List<Node>> result = new Dictionary<int, List<Node>>();
            while (depth2 < maxDepth2 || (open2.Count == 0))
            {
                //expanduj
                Node n = open2.First.Value;
                open2.RemoveFirst();
                closed2.AddLast(n);
                foreach (var item in table.GetSourceStations(n.Info.StationId, n.Info.ArrivalLines))
                {
                    Node newNode = new Node()
                    {
                        Parent = n,
                        Depth = n.Depth + 1,
                        Children = new List<Node>(),
                        Info = new NodeInfo()
                        {
                            StationId = item[0].Start,
                        }
                    };
                    //pridavanie liniek DO
                    newNode.Info.ArrivalLines = new List<Line>();
                    foreach (var line in item)
                    {
                        Line newLine = new Line() { LineID = line.Line, Distance = line.Distance };
                        /*
                        if (visitedLines.ContainsKey(line.Line) == false)
                        {
                            newNode.Info.ArrivalLines.Add(newLine);
                            visitedLines.Add(line.Line, newLine);
                        }
                        */
                        newNode.Info.ArrivalLines.Add(newLine);
                    }

                    n.Children.Add(newNode);
                    open2.AddLast(newNode);

                    if (!result.ContainsKey(newNode.Info.StationId))
                    {
                        result.Add(newNode.Info.StationId, new List<Node>());
                        result[newNode.Info.StationId].Add(newNode);
                    }
                    else
                    {
                        result[newNode.Info.StationId].Add(newNode);
                    }
                }


                //nie je idealne
                depth2 = n.Depth;
            }
            //TODO: Spytat sa martina, odoberam poslednu lebo ta nepatri do toho
            Node lastNode = closed2.Last.Value;
            closed2.RemoveLast();
            maxDepth2++;
            result.Remove(lastNode.Info.StationId);
            return result;
        }
    }

    public class NodeInfo
    {
        public List<Line> ArrivalLines { get; set; }
        public int Time { get; set; }
        public int StationId { get; set; }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            sb.Append(StationId.ToString());
            sb.Append(" [");
            for (int i = 0; i < ArrivalLines.Count; i++)
            {
                sb.Append(ArrivalLines[i].LineID.ToString() + ",");
            }
            sb.Append("]");
            return sb.ToString();


        }

    }

    public class Line
    {
        public int LineID { get; set; }
        public int Distance { get; set; }
        public int Time { get; set; }

        public override string ToString()
        {
            return "[" + LineID + ", d:" + Distance + "]";
        }
    }

    class Node
    {
        public Node Parent { get; set; }
        public NodeInfo Info { get; set; }
        public List<Node> Children { get; set; }
        public int Depth { get; set; }

        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            sb.Append(Info.StationId.ToString());
            sb.Append(" [");
            for (int i = 0; i < Info.ArrivalLines.Count; i++)
            {
                sb.Append(Info.ArrivalLines[i].LineID.ToString() + ",");
            }
            sb.Append("]");
            return sb.ToString();


        }
    }
}
